#include <string>
#include <vector>
#include <functional>
#include <unordered_map>

using namespace std;

// 959. 由斜杠划分区域
class Solution1
{
public:
    int regionsBySlashes(vector<string>& grid) 
    {
        int n = grid.size();
        int size = 4 * n * n;
        vector<int> ufs(size, -1);

        auto Find = [&ufs](int x)
        {
            int root = x;
            while(ufs[root] >= 0)
            {
                root = ufs[root];
            }
            while(ufs[x] >= 0)
            {
                int parent = ufs[x];
                ufs[x] = root;
                x = parent;
            }
            return root;
        };

        auto Union = [&](int u, int v)
        {
            int root1 = Find(u);
            int root2 = Find(v);

            if(abs(ufs[root1] < abs(ufs[root2]))) 
                swap(root1, root2);

            if(root1 != root2)
            {
                ufs[root1] += ufs[root2];
                ufs[root2] = root1;
            }
        };

        for(int i = 0; i < n; ++i)
        {
            string& str = grid[i];
            for(int j = 0; j < n; ++j)
            {
                char ch = str[j];
                int index = 4 * (i * n + j);
                // 单元格内合并
                if(ch == '/')
                {
                    Union(index, index + 3);
                    Union(index + 1, index + 2);
                }
                else if(ch == '\\')
                {
                    Union(index, index + 1);
                    Union(index + 2, index + 3);
                }
                else
                {
                    Union(index, index + 1);
                    Union(index + 1, index + 2);
                    Union(index + 2, index + 3);
                }

                // 单元格间合并
                if(j + 1 < n)
                {
                    Union(index + 1, 4 * (i * n + j + 1) + 3);
                }
                if(i + 1 < n)
                {
                    Union(index + 2, 4 * ((i + 1) * n + j));
                }
            }
        }

        int ret = 0;
        for(int i = 0; i < size; ++i)
        {
            if(ufs[i] < 0) ++ret;
        }

        return ret;
    }
};

class UnionFind
{
public:
    int Find(int x)
    {
        if(!ufs.count(x))
        {
            ufs[x] = -1;
        }
        // int root = x;
        // while(ufs[root] >= 0)
        // {
        //     root = ufs[root];
        // }
        // while(ufs[x] >= 0)
        // {
        //     int parent = ufs[x];
        //     ufs[x] = root;
        //     x = parent;
        // }
        // return root;
        return ufs[x] < 0 ? x : ufs[x] = Find(ufs[x]);
    }

    void Union(int u, int v)
    {
        int root1 = Find(u);
        int root2 = Find(v);
        if(root1 != root2)
        {
            ufs[root1] += ufs[root2];
            ufs[root2] = root1;
        }
    }

    int setSize()
    {
        int ret = 0;
        for(auto& [child, parent] : ufs)
        {
            if(parent < 0) ++ret;
        }
        return ret;
    }

private:
    unordered_map<int, int> ufs;
};

// 947. 移除最多的同行或同列石头
class Solution2
{
public:
    int removeStones(vector<vector<int>>& stones) 
    {
        UnionFind ufs;
        int n = stones.size();
        for(int i = 0; i < n; ++i)
        {
            ufs.Union(stones[i][0], stones[i][1] + 10001);
        }
        return n - ufs.setSize();
    }   
};

// 839. 相似字符串组
class Solution3
{
private:
    bool check(const string& s1, const string& s2)
    {
        int diff = 0;
        int n = s1.size();
        for(int i = 0; i < n; ++i)
        {
            if(s1[i] != s2[i]) ++diff;
            if(diff > 2) return false;
        }
        return true;
    }

public:
    int numSimilarGroups(vector<string>& strs) 
    {
        int n = strs.size();
        vector<int> ufs(n, -1);
        function<int(int)> Find = [&](int x)
        {
            // int root = x;
            // while(ufs[root] >= 0)
            // {
            //     root = ufs[root];
            // }
            // while(ufs[x] >= 0)
            // {
            //     int parent = ufs[x];
            //     ufs[x] = root;
            //     x = parent;
            // }
            // return root;
            return ufs[x] < 0 ? x : ufs[x] = Find(ufs[x]);
        };

        for(int i = 0; i < n; ++i)
        {
            for(int j = i + 1; j < n; ++j)
            {
                int root1 = Find(i);
                int root2 = Find(j);
                if(root1 == root2) continue;

                if(check(strs[i], strs[j]))
                {
                    ufs[root1] += ufs[root2];
                    ufs[root2] = root1;
                }
            }
        }

        int ret = 0;
        for(int i = 0; i < n; ++i)
        {
            if(ufs[i] < 0) ++ret;
        }
        return ret;
    }
};

// 854. 相似度为 K 的字符串
class Solution4
{
private:
    int ret = INT_MAX;
    int path = 0;
    int n;

    void DFS(string& s1, string& s2, int index)
    {
        if(index == n)
        {
            ret = min(ret, path);
            return;
        }

        if(path >= ret) return;

        if(s1[index] != s2[index])
        {
            for(int i = index + 1; i < n; ++i)
            {
                if(s2[i] != s1[i] && s2[i] == s1[index])
                {
                    swap(s2[i], s2[index]);
                    ++path;
                    // 去匹配下一个字符
                    DFS(s1, s2, index + 1);
                    // 回溯
                    --path;
                    swap(s2[i], s2[index]);
                    // 一次交换就让两对字符匹配，肯定是最小的交换次数
                    // 不需要再向后进行遍历了
                    if(s2[i] == s1[index] && s2[index] == s1[i]) break;
                }
            }
        }
        else
        {
            DFS(s1, s2, index + 1); // 去匹配下一个字符
        }
    }

public:
    int kSimilarity(string s1, string s2) 
    {
        n = s1.size();
        DFS(s1, s2, 0);
        return ret;
    }
};

// 765. 情侣牵手
class Solution5
{
public:
    int minSwapsCouples(vector<int>& row) 
    {
        int len = row.size();
        int n = len / 2;
        vector<int> ufs(n, -1);

        function<int(int)> Find = [&](int x)
        {
            return ufs[x] < 0 ? x : ufs[x] = Find(ufs[x]);
        };

        for(int i = 0; i < len; i += 2)
        {
            int root1 = Find(row[i] / 2);
            int root2 = Find(row[i + 1] / 2);
            if(root1 != root2)
            {
                ufs[root1] += ufs[root2];
                ufs[root2] = root1;
            }
        }

        int ret = n;
        for(int i = 0; i < n; ++i)
        {
            if(ufs[i] < 0) --ret;
        }
        return ret;
    }
};

// 1361. 验证二叉树
class Solution6
{
public:
    bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) 
    {
        // 统计节点的入度
        vector<int> inDegree(n);
        for(int i = 0; i < n; ++i)
        {
            if(leftChild[i] != -1) ++inDegree[leftChild[i]];
            if(rightChild[i] != -1) ++inDegree[rightChild[i]];
        }

        // 入度为 0 的节点就是根节点，记录根节点的数量和下标
        int rootCount = 0;
        int rootIndex = 0;
        for(int i = 0; i < n; ++i)
        {
            if(inDegree[i] == 0)
            {
                ++rootCount;
                rootIndex = i;
            }
            // 有多个根节点，意味着有多棵树，这里
            // 排除了有多棵树的可能性
            if(rootCount > 1) return false; 
        }

        // 下面的逻辑都是利用并查集来判断一棵树中有没有成环
        // 并查集初始化：如果 ufs[i] 为正数表示，i 节点的父节点是 ufs[i]
        // 如果 ufs[i] 为负数，则 i 节点就是一个集合中的老大（在本题中老大
        // 意味着是树的根节点），此时 ufs[i] 的绝对值就是集合中节点的个数
        // 换成其他题目，ufs 中负数的个数就是集合的个数
        vector<int> ufs(n, -1);
        // Find 找出父节点的同时进行路径压缩
        function<int(int)> Find = [&](int x)
        {
            return ufs[x] < 0 ? x : ufs[x] = Find(ufs[x]);
        };

        // 将 v 添加到 u 所在的集合中
        auto Union = [&](int u, int v)
        {
            int root1 = Find(u);
            int root2 = Find(v);
            if(root1 != root2)
            {
                ufs[root1] += ufs[root2];
                ufs[root2] = root1;
            }
        };

        // 判断 u 和 v 是不是在同一个集合中
        auto Same = [&](int u, int v)
        {
            return Find(u) == Find(v);
        };

        for(int i = 0; i < n; ++i)
        {
            if(leftChild[i] != -1)
            {
                if(Same(leftChild[i], i)) // 成环了
                    return false;
                else
                    Union(i, leftChild[i]);
            }

            if(rightChild[i] != -1)
            {
                if(Same(rightChild[i], i)) // 成环了
                    return false;
                else
                    Union(i, rightChild[i]);
            }
        }

        // 没有成环，那么一定一棵合法的二叉树
        return true;
    }
};